package net.projecteuler.prob;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;

public class Problem66 implements Runnable {
	
	private final static int maxD = 1000;
	private BigInteger bigMax = new BigInteger("100000");
	
	@Override
	public void run() {
		for(int i = 2; i < 1000; i++){
			if(Math.round(Math.sqrt(i)) == Math.sqrt(i))
				continue;

			BigInteger bigX = solveDiophantine(i);
			System.out.println(i + " : " + bigX);
		}
	}
	
	public BigInteger solveDiophantine(int D){
		BigInteger bigD = BigInteger.valueOf(D);

		BigInteger bigY = BigInteger.ZERO;
		while(true){
			bigY = bigY.add(BigInteger.ONE);
			BigInteger bigXsq = bigD.multiply(bigY).multiply(bigY).add(BigInteger.ONE);
			BigInteger bigX = isSquare(bigXsq);
			if(bigX != null)
				return bigX;
			
			if(bigY.compareTo(bigMax) > 0)
				break;
		}
		
		return null;
	}
	
	private BigInteger isSquare(BigInteger big){
		BigDecimal sqrt = sqrt(new BigDecimal(big), 15);
		BigDecimal round = sqrt.setScale(0, RoundingMode.HALF_UP);
		if(sqrt.compareTo(round) == 0)
			return round.toBigInteger();
		return null;
	}
	
	public static BigDecimal sqrt(BigDecimal in, int scale){
	    BigDecimal sqrt = new BigDecimal(1);
	    sqrt.setScale(scale + 3, RoundingMode.FLOOR);
	    BigDecimal store = new BigDecimal(in.toString());
	    boolean first = true;
	    do{
	        if (!first){
	            store = new BigDecimal(sqrt.toString());
	        }
	        else first = false;
	        store.setScale(scale + 3, RoundingMode.FLOOR);
	        sqrt = in.divide(store, scale + 3, RoundingMode.FLOOR).add(store).divide(
	                BigDecimal.valueOf(2), scale + 3, RoundingMode.FLOOR);
	    }while (!store.equals(sqrt));
	    return sqrt.setScale(scale, RoundingMode.FLOOR);
	}
}
